package com.leetcode.algorithm.y22.m07.w4;

/**
 * 560. 和为 K 的子数组
 * 
 * https://leetcode.cn/problems/subarray-sum-equals-k/
 * 
 * @author jie.deng
 *
 */
class Question0560Solution01 {

	// 超出内存限制
	public int subarraySum(int[] nums, int k) {
		int len = nums.length;

		// dp[i][j] 表示 num[i...j]之和
		int[][] dp = new int[len][len];
		int cnt = 0;
		for (int i = 0; i < len; i++) {
			dp[i][i] = nums[i];
			if (dp[i][i] == k) {
				cnt++;
			}
		}
		// dp[0][0],dp[1][1],...
		// dp[0][1]
		// dp[0][2],dp[1][2]
		// dp[0][3],dp[1][3],dp[2][3]
		for (int j = 1; j < len; j++) {
			for (int i = 0; i < j; i++) {
				dp[i][j] = dp[i][j - 1] + nums[j];
				if (dp[i][j] == k) {
					cnt++;
				}
			}
		}
		return cnt;
	}

}